﻿/**
 * @file std_list.h
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 使用 C API 的接口形式实现 双向链表 容器。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __STD_LIST_H__
#define __STD_LIST_H__

#include "std_comm.h"

////////////////////////////////////////////////////////////////////////////////

#ifdef __cplusplus
extern "C"
{
#endif // __cplusplus

////////////////////////////////////////////////////////////////////////////////

//====================================================================

// 
// xstd_list_t 的相关数据类型定义
// 

#define XLST_FALSE           XSTD_FALSE
#define XLST_TRUE            XSTD_TRUE
#define XLST_NULL            XSTD_NULL

typedef xstd_void_t          xlst_void_t;
typedef xstd_bool_t          xlst_bool_t;
typedef xstd_size_t          xlst_size_t;
typedef xstd_elem_t          xlst_elem_t;
typedef xstd_ctxt_t          xlst_ctxt_t;
typedef xstd_func_compare_t  xlst_cmpfunc_t;
typedef xstd_func_confirm_t  xlst_cfmfunc_t;

/** 声明 xstd_list_t 对象指针类型 */
typedef struct xstd_list_t *  xlst_this_t;

/** 声明 xstd_list_t 的迭代器类型 */
typedef struct xlst_node_t *  xlst_iter_t;

//====================================================================

// 
// xstd_list_t 的相关操作接口
// 

/**********************************************************/
/**
 * @brief 返回内部的 sizeof(xstd_list_t) 值。
 */
xlst_size_t std_list_sizeof(void);

/**********************************************************/
/**
 * @brief 创建 xstd_list_t 对象。
 * @note 
 * 1. 入参 xlst_ctxt 中的 内存管理对象，若其中的某个回调函数
 *    为 XLST_NULL，则配置成全局管理对象对应函数接口。
 * 2. 可使用 @see std_list_destroy() 销毁对象。
 * 
 * @param [in ] xlst_ctxt : 链表所存储节点的类型上下文描述信息。
 * 
 * @return xlst_this_t : xstd_list_t 对象指针。
 */
xlst_this_t std_list_create(xlst_ctxt_t xlst_ctxt);

/**********************************************************/
/**
 * @brief 销毁 xstd_list_t 对象，其由 @see std_list_create() 创建。
 */
xlst_void_t std_list_destroy(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 创建 xstd_list_t 对象。
 * @note 
 * 1. 入参 xlst_ctxt 中的 内存管理对象，若其中的某个回调函数
 *    为 XLST_NULL，则配置成全局管理对象对应函数接口。
 * 2. 可使用 @see std_list_emplace_destroy() 销毁对象。
 * 
 * @param [in,out] xlst_this : 
 * 存储 xstd_list_t 对象的缓存，
 * 其大小不可小于 std_list_sizeof() 的返回值。
 * 
 * @param [in    ] xlst_ctxt : 链表所存储节点的类型上下文描述信息。
 * 
 * @return xlst_this_t : xstd_list_t 对象指针。
 */
xlst_this_t std_list_emplace_create(
                xlst_this_t xlst_this,
                xlst_ctxt_t xlst_ctxt);

/**********************************************************/
/**
 * @brief 在指定缓存上销毁 xstd_list_t 对象。
 * @note  xstd_list_t 对象是由 @see std_list_emplace_create() 创建。
 */
xlst_void_t std_list_emplace_destroy(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的 上下文信息。
 */
xlst_ctxt_t std_list_ctxt(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的 类型标识。
 */
xlst_size_t std_list_etype(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象中的节点数量。
 */
xlst_size_t std_list_size(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 判断 xstd_list_t 对象是否为空。
 */
xlst_bool_t std_list_empty(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象可容纳最大节点数量。
 */
xlst_size_t std_list_maxsize(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的前端节点值。
 */
xlst_elem_t std_list_front(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的后端节点值。
 */
xlst_elem_t std_list_back(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 清除 xstd_list_t 对象中的所有节点。
 */
xlst_void_t std_list_clear(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 向 xstd_list_t 对象插入新的节点。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xiter_pos : 插入节点的所在位置。
 * @param [in    ] xlst_elem : 插入节点的所存储元素。
 * 
 * @return xlst_iter_t : 返回新插入节点对应的迭代器。
 */
xlst_iter_t std_list_insert(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_pos,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 向 xstd_list_t 对象安放新的节点，元素以 右值move 方式进行存储。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xiter_pos : 安放新节点的所在位置。
 * @param [in    ] xlst_elem : 安放新节点的所存储元素。
 * 
 * @return xlst_iter_t : 返回新安放节点对应的迭代器。
 */
xlst_iter_t std_list_emplace(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_pos,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 从 xstd_list_t 对象中删除指定的节点。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xiter_pos : 删除节点的所在位置。
 * 
 * @return xlst_iter_t : 返回 xiter_pos 的后继节点迭代器。
 */
xlst_iter_t std_list_erase(xlst_this_t xlst_this, xlst_iter_t xiter_pos);

/**********************************************************/
/**
 * @brief 从 xstd_list_t 对象中删除 [ xiter_first, xiter_last ) 子串。
 * 
 * @param [in,out] xlst_this   : xstd_list_t 对象。
 * @param [in    ] xiter_first : 迭代区域的起始位置。
 * @param [in    ] xiter_last  : 迭代区域的结束位置。
 * 
 * @return xlst_iter_t : 返回 xiter_last 迭代器。
 */
xlst_iter_t std_list_erase_range(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_first,
                xlst_iter_t xiter_last);

/**********************************************************/
/**
 * @brief 将 多个（相同的）节点值 指派给 xstd_list_t 对象。
 * @note  该操作会更新整个 xstd_list_t 对象，包括节点数量。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xlst_size : 指派的节点数量。
 * @param [in    ] xlst_elem : 指派的节点值。
 */
xlst_void_t std_list_assign(
                xlst_this_t xlst_this,
                xlst_size_t xlst_size,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief
 * 调整 xstd_list_t 对象中的节点数量到 指定值。
 * 若 指定值 多于原有的节点数量，则使用 指定节点元素 补充多出的节点。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xlst_size : 所要调整到的节点数量。
 * @param [in    ] xlst_elem : 补充操作时使用的节点元素。
 */
xlst_void_t std_list_resize(
                xlst_this_t xlst_this,
                xlst_size_t xlst_size,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 向 xstd_list_t 对象前端新增一个节点。
 */
xlst_void_t std_list_push_front(
                xlst_this_t xlst_this,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 向 xstd_list_t 对象前端新增一个节点，元素以 右值move 方式进行存储。
 */
xlst_void_t std_list_push_mfront(
                xlst_this_t xlst_this,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 将 xstd_list_t 对象的前端节点弹出（删除）。
 */
xlst_void_t std_list_pop_front(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 向 xstd_list_t 对象后端新增一个节点。
 */
xlst_void_t std_list_push_back(
                xlst_this_t xlst_this,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 向 xstd_list_t 对象后端新增一个节点，元素以 右值move 方式进行存储。
 */
xlst_void_t std_list_push_mback(
                xlst_this_t xlst_this,
                xlst_elem_t xlst_elem);

/**********************************************************/
/**
 * @brief 将 xstd_list_t 对象的后端节点弹出（删除）。
 */
xlst_void_t std_list_pop_back(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 对 xstd_list_t 对象进行反序操作。
 */
xlst_void_t std_list_reverse(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 
 * 将 xstd_list_t 对象中的区间 [ xiter_first, xiter_last ) 
 * 切换至指定位置。
 * @note 
 * 所指定的目标位置 xiter_pos 不能
 * 位于 [ xiter_first, xiter_last ) 区间内。
 * 
 * @param [in,out] xlst_this   : xstd_list_t 对象。
 * @param [in    ] xiter_pos   : 切换所至的目标位置。
 * @param [in    ] xiter_first : 子串区间的起始位置。
 * @param [in    ] xiter_last  : 子串区间的结束位置。
 */
xlst_void_t std_list_splice(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_pos,
                xlst_iter_t xiter_first,
                xlst_iter_t xiter_last);

/**********************************************************/
/**
 * @brief 
 * 将另一同类型的 xlst_other 对象内的所有节点拼接到
 * 现有的 xlst_this 对象中指定位置。
 * @note 
 * xlst_this 与 xlst_other 的 类型标识 与 节点元素类型 必须一致。
 * 操作完成后，xlst_other 将会被清空。
 * 
 * @param [in,out] xlst_this  : xstd_list_t 对象。
 * @param [in    ] xiter_pos  : 拼接位置（xlst_this 中的节点位置）。
 * @param [in,out] xlst_other : 另一同类型的 xstd_list_t 对象。
 */
xlst_void_t std_list_splice_other(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_pos,
                xlst_this_t xlst_other);

/**********************************************************/
/**
 * @brief 
 * 将另一同类型的 xlst_other 对象内的 （区间）节点子串
 * 拼接到现有的 xlst_this 对象中。
 * @note 
 * 1. xlst_this 与 xlst_other 的 类型标识 与 节点元素类型 必须一致。
 * 2. 若 xlst_this != xlst_other 时，
 *    xlst_other的（区间）节点子串 将会被转移到 xlst_this 中。
 * 3. 若 xlst_this == xlst_other 时，
 *    则要求 xiter_pos 必须在区间 [ xiter_first, xiter_last ) 之外。
 * 
 * @param [in,out] xlst_this   : xstd_list_t 对象。
 * @param [in    ] xiter_pos   : 拼接位置（xlst_this 中的节点位置）。
 * @param [in,out] xlst_other  : 另一同类型的 xstd_list_t 对象
 * @param [in    ] xiter_first : xlst_other 的子串区间的起始位置。
 * @param [in    ] xiter_last  : xlst_other 的子串区间的结束位置。
 */
xlst_void_t std_list_splice_range(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_pos,
                xlst_this_t xlst_other,
                xlst_iter_t xiter_first,
                xlst_iter_t xiter_last);

/**********************************************************/
/**
 * @brief 对 xstd_list_t 对象进行排序操作。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xfunc_cmp : 进行比较（小于）判断的回调函数。
 */
xlst_void_t std_list_sort(
                xlst_this_t xlst_this,
                xlst_cmpfunc_t xfunc_cmp);

/**********************************************************/
/**
 * @brief 把两个已排序好的 xstd_list_t 对象合并到 xlst_this 中。
 * @note 
 * 1. 合并操作，会把 xlst_other 对象内所有节点转移至 xlst_this 中。
 * 2. 该操作，要求两个链表对象是已排序的，若未排序，则结果不可预测。
 * 
 * @param [in,out] xlst_this  : 被移入节点的 xstd_list_t 对象。
 * @param [in,out] xlst_other : 被移出节点的 xstd_list_t 对象。
 * @param [in    ] xfunc_cmp  : 进行比较（小于）判断的回调函数。
 */
xlst_void_t std_list_merge(
                xlst_this_t xlst_this,
                xlst_this_t xlst_other,
                xlst_cmpfunc_t xfunc_cmp);

/**********************************************************/
/**
 * @brief 
 * 从 xstd_list_t 对象中移除 移除所有连续重复的节点元素。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xfunc_cmp : 进行比较（等于）判断的回调函数。
 * 
 * @return xlst_size_t : 被移除的节点数量。
 */
xlst_size_t std_list_unique(
                xlst_this_t xlst_this,
                xlst_cmpfunc_t xfunc_cmp);

/**********************************************************/
/**
 * @brief 在 xstd_list_t 对象中查找出现指定 元素 的首个节点。
 * 
 * @param [in ] xlst_this : xstd_list_t 对象。
 * @param [in ] xiter_pos : 查找操作的起始位置。
 * @param [in ] xlst_elem : 指定查找的 元素。
 * @param [in ] xfunc_cmp : 进行比较（等于）判断的回调函数。
 * 
 * @return xlst_iter_t : 
 * 返回对应的节点迭代器，失败时（未找到），返回链表的末端迭代器。
 */
xlst_iter_t std_list_find(
                xlst_this_t xlst_this,
                xlst_iter_t xiter_pos,
                xlst_elem_t xlst_elem,
                xlst_cmpfunc_t xfunc_cmp);

/**********************************************************/
/**
 * @brief 从 xstd_list_t 对象中移除与指定元素值相等的节点。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xlst_elem : 指定要移除的元素值。
 * @param [in    ] xfunc_cmp : 进行比较（等于）判断的回调函数。
 * 
 * @return xlst_size_t : 返回被移除节点的数量。
 */
xlst_size_t std_list_remove(
                xlst_this_t xlst_this,
                xlst_elem_t xlst_elem,
                xlst_cmpfunc_t xfunc_cmp);

/**********************************************************/
/**
 * @brief 
 * 从 xstd_list_t 对象中移除 满足特定条件（使用回调函数进行判断）的节点。
 * 
 * @param [in,out] xlst_this : xstd_list_t 对象。
 * @param [in    ] xfunc_cfm : 进行条件判断的回调函数。
 * 
 * @return xlst_size_t : 返回被移除节点的数量。
 */
xlst_size_t std_list_remove_if(
                xlst_this_t xlst_this,
                xlst_cfmfunc_t xfunc_cfm);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的起始节点迭代器。
 */
xlst_iter_t std_list_begin(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 迭代器 的后继节点迭代器。
 */
xlst_iter_t std_list_next(xlst_iter_t xiter_trav);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的结束节点迭代器。
 */
xlst_iter_t std_list_end(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的反向起始节点迭代器。
 */
xlst_iter_t std_list_rbegin(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 返回 反向迭代器 的后继节点迭代器。
 */
xlst_iter_t std_list_rnext(xlst_iter_t xiter_trav);

/**********************************************************/
/**
 * @brief 返回 xstd_list_t 对象的反向结束节点迭代器。
 */
xlst_iter_t std_list_rend(xlst_this_t xlst_this);

/**********************************************************/
/**
 * @brief 读取节点迭代器下存储的 元素。
 */
xlst_elem_t std_list_elem(xlst_iter_t xiter_node);

////////////////////////////////////////////////////////////////////////////////

/** 
 * @brief 
 * 为 xstd_list_t 的基础数据类型容器，
 * 定义简化版操作接口的宏。
 */
#define XSTD_LIST_TYPE_FUNC(xtype, xname)               \
                                                        \
static inline xlst_this_t                               \
    std_list_create_##xname(void)                       \
{                                                       \
    return std_list_create(                             \
                &xstd_ctxt_##xname);                    \
}                                                       \
                                                        \
static inline xtype                                     \
    std_list_front_##xname(xlst_this_t xlst_this)       \
{                                                       \
    return *(xtype *)std_list_front(xlst_this);         \
}                                                       \
                                                        \
static inline xtype                                     \
    std_list_back_##xname(xlst_this_t xlst_this)        \
{                                                       \
    return *(xtype *)std_list_back(xlst_this);          \
}                                                       \
                                                        \
static inline xlst_iter_t                               \
    std_list_insert_##xname(                            \
                xlst_this_t xlst_this,                  \
                xlst_iter_t xiter_pos,                  \
                xtype xlst_elem)                        \
{                                                       \
    return std_list_insert(                             \
                xlst_this,                              \
                xiter_pos,                              \
                &xlst_elem);                            \
}                                                       \
                                                        \
static inline xlst_void_t                               \
    std_list_assign_##xname(                            \
                xlst_this_t xlst_this,                  \
                xlst_size_t xlst_size,                  \
                xtype xlst_elem)                        \
{                                                       \
    std_list_assign(                                    \
        xlst_this,                                      \
        xlst_size,                                      \
        &xlst_elem);                                    \
}                                                       \
                                                        \
static inline xlst_void_t                               \
    std_list_resize_##xname(                            \
                xlst_this_t xlst_this,                  \
                xlst_size_t xlst_size,                  \
                xtype xlst_elem)                        \
{                                                       \
    std_list_resize(                                    \
        xlst_this,                                      \
        xlst_size,                                      \
        &xlst_elem);                                    \
}                                                       \
                                                        \
static inline xlst_void_t                               \
    std_list_push_front_##xname(                        \
                xlst_this_t xlst_this,                  \
                xtype xlst_elem)                        \
{                                                       \
    std_list_push_front(xlst_this, &xlst_elem);         \
}                                                       \
                                                        \
static inline xlst_void_t                               \
    std_list_push_back_##xname(                         \
                xlst_this_t xlst_this,                  \
                xtype xlst_elem)                        \
{                                                       \
    std_list_push_back(xlst_this, &xlst_elem);          \
}                                                       \
                                                        \
static inline xlst_iter_t                               \
    std_list_find_##xname(                              \
                xlst_this_t xlst_this,                  \
                xlst_iter_t xiter_pos,                  \
                xtype xlst_elem,                        \
                xlst_cmpfunc_t xfunc_cmp)               \
{                                                       \
    return std_list_find(                               \
                xlst_this,                              \
                xiter_pos,                              \
                &xlst_elem,                             \
                xfunc_cmp);                             \
}                                                       \
                                                        \
static inline xlst_size_t                               \
    std_list_remove_##xname(                            \
                xlst_this_t xlst_this,                  \
                xtype xlst_elem,                        \
                xlst_cmpfunc_t xfunc_cmp)               \
{                                                       \
    return std_list_remove(                             \
                xlst_this,                              \
                &xlst_elem,                             \
                xfunc_cmp);                             \
}                                                       \
                                                        \
static inline xtype                                     \
    std_list_elem_##xname(xlst_iter_t xiter_node)       \
{                                                       \
    return *(xtype *)std_list_elem(xiter_node);         \
}

//====================================================================

XSTD_LIST_TYPE_FUNC(xstd_char_t   , char   )  // 对应 xstd_char_t    类型
XSTD_LIST_TYPE_FUNC(xstd_uchar_t  , uchar  )  // 对应 xstd_uchar_t   类型
XSTD_LIST_TYPE_FUNC(xstd_int8_t   , int8   )  // 对应 xstd_int8_t    类型
XSTD_LIST_TYPE_FUNC(xstd_int16_t  , int16  )  // 对应 xstd_int16_t   类型
XSTD_LIST_TYPE_FUNC(xstd_int32_t  , int32  )  // 对应 xstd_int32_t   类型
XSTD_LIST_TYPE_FUNC(xstd_int64_t  , int64  )  // 对应 xstd_int64_t   类型
XSTD_LIST_TYPE_FUNC(xstd_uint8_t  , uint8  )  // 对应 xstd_uint8_t   类型
XSTD_LIST_TYPE_FUNC(xstd_uint16_t , uint16 )  // 对应 xstd_uint16_t  类型
XSTD_LIST_TYPE_FUNC(xstd_uint32_t , uint32 )  // 对应 xstd_uint32_t  类型
XSTD_LIST_TYPE_FUNC(xstd_uint64_t , uint64 )  // 对应 xstd_uint64_t  类型
XSTD_LIST_TYPE_FUNC(xstd_long_t   , long   )  // 对应 xstd_long_t    类型
XSTD_LIST_TYPE_FUNC(xstd_llong_t  , llong  )  // 对应 xstd_llong_t   类型
XSTD_LIST_TYPE_FUNC(xstd_ulong_t  , ulong  )  // 对应 xstd_ulong_t   类型
XSTD_LIST_TYPE_FUNC(xstd_ullong_t , ullong )  // 对应 xstd_ullong_t  类型
XSTD_LIST_TYPE_FUNC(xstd_float_t  , float  )  // 对应 xstd_float_t   类型
XSTD_LIST_TYPE_FUNC(xstd_double_t , double )  // 对应 xstd_double_t  类型
XSTD_LIST_TYPE_FUNC(xstd_ldouble_t, ldouble)  // 对应 xstd_ldouble_t 类型
XSTD_LIST_TYPE_FUNC(xstd_handle_t , handle )  // 对应 xstd_handle_t  类型

////////////////////////////////////////////////////////////////////////////////

#ifdef __cplusplus
}; // extern "C"
#endif // __cplusplus

////////////////////////////////////////////////////////////////////////////////

#endif // __STD_LIST_H__
